Booth recoding is a useful tool in reducing the number of steps and circuitry required to multiply a multi-bit multiplicand "a" (a[m:0]) by a multiplier "b" (b[n:0]), where "m" and "n" are non-negative integers.
In the remainder of this application, unless otherwise noted, to illustrate the invention, we will use as an example a 4 bit by 3 bit multiplication. That is, "m" is 4, "n" is 3, "a" has a value -4.sub.10, and "b" has a value -7.sub.10. Hence, bits a[4:0] are a binary signed representation of "a" having respective binary values 1, 1, 1, 0, and 0, and bits b[3:0] are a binary signed representation of "b" having respective binary values 1, 0, 0, and 1. However, the present invention applies to booth multiplication of integer or fractional multiplicands and multipliers of any length and value.
The following shows a longhand form for multiplying "a" by "b". ##EQU1## As is known in the art, a 2's complement number can be extended to any bit length. Such sign extension is performed by padding on the left with "1" bits for negative numbers (e.g., partial product #1) and "0" bits for non-negative numbers (e.g., partial products #2, #3, and #4). Note that bit b[3] has a weight of negative 8.
The above longhand form is referred to as radix-2 multiplication. In radix-2 multiplication, each multiplier bit b[3], b[2], b[1], and b[0] is multiplied by the entire multiplicand "a" to produce a respective partial product. The number of partial products (e.g., four in the above example) equals the number of digits "n+1" in the multiplier "b".
However, a conventional radix-4 modified booth recoding technique reduces the number of required partial products in half compared to the above radix-2 multiplication as described below. For example, the operation a.times.b produces only integer[(n+2)/2] partial products (e.g., two partial products for bits b[3:0]).
FIG. 1 shows a conventional booth recoding circuit 100 which includes a booth recoder 110 having input lines 101-103 carrying signals representing respective bits b[1:-1] where b[-1] is a dummy bit having a value set at a binary zero. Booth recoder 110 receives the signal representing bits b[1:-1] (e.g., 0, 1, and 0, respectively) and outputs three signals representing bits NEG, ZERO, and TWO over respective lines 111-113 to partial product generator ("PPG") 120. Table 1 shows the values of NEG, ZERO, and TWO that booth recoder 110 outputs for each permutation of input bits b[2i-1:2i-3] (i.e., b[1:-1] in this example) and the first partial product PP1 output by PPG 120. Note that "w.sub.a " is the weight of the least significant bit a[0] of "a", and "w.sub.b " is the weight of the least significant bit b[0] of "b".
TABLE 1 ______________________________________ Values of Value of Bits b[2i-1:2i-3] NEG, ZERO, TWO PPG Output Respectively Respectively (PPi) ______________________________________ 0, 0, 0 1, 1, 0 zero 0, 0, 1 0, 0, 0 2.sup.(2i-2) aw.sub.a w.sub.b 0, 1, 0 0, 0, 0 2.sup.(2i-2) aw.sub.a w.sub.b 0, 1, 1 0, 0, 1 2.sup.(2i-1) aw.sub.a w.sub.b 1, 0, 0 1, 0, 1 (-1)2.sup.(2i-1) aw.sub.a w.sub.b 1, 0, 1 1, 0, 0 (-1)2.sup.(2i-2) aw.sub.a w.sub.b 1, 1, 0 1, 0, 0 (-1)2.sup.(2i-2) aw.sub.a w.sub.b 1, 1, 1 0, 1, 0 zero ______________________________________
For clarity, "w.sub.a " and "w.sub.b " are equal to one in the above example since "a" and "b" are integer values. PPG 120 has input lines 111-113 carrying signals represented respective bits NEG, ZERO, and TWO and also has an input line 114 which carries a signal representing bits a[4:0]. According to Table 1, a high ZERO bit indicates that the partial product is zero regardless of the value of the NEG and TWO bits. If only the NEG bit is high, the partial product is -a while if only the NEG and TWO bits are high, the partial product is -2a. If only the TWO bit is high, the partial product is 2a while if no bits are high, the partial product is a.
A similar booth recoder and partial product generator are provided and similarly configured for each set of bits b[2i-1:2i-3] for each "i" where "i" is the set of all positive integers equal to or less than (n+2)/2 (e.g., "i" is 1 and 2 if "n" equals 3). Booth recoding is a technique that is known in the art and is described in, for example, Principles of CMOS VLSI design, A Systems Perspective (ISBN: 0-201-53376-6) on pages 547-555, and in, for example, Modern VLSI design. A Systems Approach (ISBN: 0-13-588377-6) on pages 235 to 238, which are incorporated herein by reference in their entirety. Sometimes, as in the above Principles of CMOS VLSI design, A Systems Perspective reference, a negated partial product is sent to adder 270 of FIG. 2 as a one's complement partial product (PP) accompanied by an increment control signal (N&lt;1&gt;) as on page 552 of Principles of CMOS VLSI design, A Systems Perspective.
It is often necessary to use booth multiplication to perform the operation shown in equation (1). EQU product=a.times.-b (1)
"-b" is obtained from "b" according to equation (2) where b' is the 1's complement (i.e., all bits b[3:0] are inverted) of "b". EQU -b=b'+W.sub.b (2)
Therefore, one conventional method to obtain "-b" is to increment the 1's complement of "b".
FIG. 2 shows a conventional circuit 200 for obtaining "product" of equation (1). Circuit 200 includes an inverter 252 which receives bus 253 carrying signals representing bits b[3:0] (e.g., 1, 0, 0, 1), inverts bits b[3:0] to obtain bits b'[3:0], and outputs signals representing bits b'[3:0] (e.g., 0, 1, 1, 0) on bus 254. Adder 260 receives the signals representing bits b'[3:0] on bus 254, receives a signal representing weight value "w.sub.b " (e.g., one) on line 251, adds the weight value "w.sub.b " to the 1's complement multiplier b', and outputs signals representing the resultant negated multiplier "-b" having bits -b[3:0] (e.g., 0, 1, 1, 1) on bus 261.
Bus 261 includes lines 262-265 which carry signals representing respective bits -b[3:0]. Booth recoders 210 and 230 receive signals representing bits -b[3:0] on lines 262-265 and receives a dummy bit -b[-1] having a binary value of zero from line 266. Booth recoders 210 and 230 send respective signals over lines 211-213 and 231-233 to respective partial product generators 220 and 240 where signals representing partial products PP1 and PP2 are output on busses 221 and 241, respectively, to adder 270 according to Table 1.
The circuit of FIG. 2 requires the use of an extra adder 260 in order to increment. Adder 260 requires space and time in order to perform the above operations. Furthermore, circuit 200 has no flexibility to selectively perform any operations other than "product=a.times.-b" of equation (1).
Therefore, what is desired is a circuit and method for flexibly performing booth multiplication operations such as "a.times.-b" using inputs "a" and "b" without using an extra adder before performing booth multiplication.